#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/08/03
# @Author   :Changshu
# @File     :practice_21.py
# 21. 合并两个有序链表

class ListNode:
	def __init__(self,val=0,next=None):
		self.val=val
		self.next=next
	def printListNode(self):
		p=self
		while p:
			print(p.val,end=' ')
			p=p.next


def mergeTwoLists(l1:ListNode,l2:ListNode)->ListNode:
	node=ListNode(0,None)
	res=node
	while l1 and l2:
		if l1.val<=l2.val:
			node.next,l1=l1,l1.next
		else:
			node.next,l2=l2,l2.next
		node=node.next
	if l1:
		node.next=l1
	if l2:
		node.next=l2
	return res.next


if __name__=='__main__':
	l1 = ListNode(1,None)
	p=l1

	p.next = ListNode(2, None)
	p=p.next

	p.next=ListNode(4,None)


	l2=ListNode(1,None)
	p=l2

	p.next=ListNode(3,None)
	p=p.next

	p.next=ListNode(4,None)

	r=mergeTwoLists(l1,l2)
	r.printListNode()
